# ν μ λ ¬(Heap Sort)
μμ μ΄μ§ νΈλ¦¬λ₯Ό κΈ°λ³ΈμΌλ‘ νλ ν(Heap) μλ£κ΅¬μ‘°λ₯Ό κΈ°λ°μΌλ‘ν μ λ ¬ λ°©μ
μμ μ΄μ§ νΈλ¦¬λ?
μ½μ ν λ μΌμͺ½λΆν° μ°¨λ‘λλ‘ μΆκ°νλ μ΄μ§ νΈλ¦¬
ν μνΈλ λΆμμ μ λ ¬
μ μν¨
μκ°λ³΅μ‘λ
νκ· | μ΅μ | μ΅μ |
---|---|---|
Ξ(nlogn) | Ξ©(nlogn) | O(nlogn) |
# κ³Όμ
- μ΅λ νμ ꡬμ±
- νμ¬ ν 루νΈλ κ°μ₯ ν° κ°μ΄ μ‘΄μ¬ν¨. 루νΈμ κ°μ λ§μ§λ§ μμμ λ°κΎΌ ν, νμ μ¬μ΄μ¦ νλ μ€μ
- νμ μ¬μ΄μ¦κ° 1λ³΄λ€ ν¬λ©΄ μ κ³Όμ λ°λ³΅
루νΈλ₯Ό λ§μ§λ§ λ Έλλ‘ λ체 (11 β 4), λ€μ μ΅λ ν ꡬμ±
μ΄μ κ°μ λ°©μμΌλ‘ μ΅λ κ°μ νλμ© λ½μλ΄λ©΄μ μ λ ¬νλ κ²μ΄ ν μνΈ
public void heapSort(int[] array) {
int n = array.length;
// max heap μ΄κΈ°ν
for (int i = n/2-1; i>=0; i--){
heapify(array, n, i); // 1
}
// extract μ°μ°
for (int i = n-1; i>0; i--) {
swap(array, 0, i);
heapify(array, i, 0); // 2
}
}
# 1λ²μ§Έ heapify
μΌλ° λ°°μ΄μ νμΌλ‘ ꡬμ±νλ μν
μμλ Έλλ‘λΆν° λΆλͺ¨λ Έλ λΉκ΅
n/2-1λΆν° 0κΉμ§ μΈλ±μ€κ° λλ μ΄μ λ?
λΆλͺ¨ λ Έλμ μΈλ±μ€λ₯Ό κΈ°μ€μΌλ‘ μΌμͺ½ μμλ Έλ (i2 + 1), μ€λ₯Έμͺ½ μμ λ Έλ(i2 + 2)μ΄κΈ° λλ¬Έ
# 2λ²μ§Έ heapify
μμκ° νλ μ κ±°λ μ΄νμ λ€μ μ΅λ νμ ꡬμ±νκΈ° μν¨
루νΈλ₯Ό κΈ°μ€μΌλ‘ μ§ν(extract μ°μ° μ²λ¦¬λ₯Ό μν΄)
public void heapify(int array[], int n, int i) {
int p = i;
int l = i*2 + 1;
int r = i*2 + 2;
//μΌμͺ½ μμλ
Έλ
if (l < n && array[p] < array[l]) {
p = l;
}
//μ€λ₯Έμͺ½ μμλ
Έλ
if (r < n && array[p] < array[r]) {
p = r;
}
//λΆλͺ¨λ
Έλ < μμλ
Έλ
if(i != p) {
swap(array, p, i);
heapify(array, n, p);
}
}
λ€μ μ΅λ νμ ꡬμ±ν λκΉμ§ λΆλͺ¨ λ Έλμ μμ λ Έλλ₯Ό swapνλ©° μ¬κ· μ§ν
ν΅μ λ ¬κ³Ό ν©λ³μ λ ¬μ μ±λ₯μ΄ μ’κΈ° λλ¬Έμ ν μ λ ¬μ μ¬μ©λΉλκ° λμ§λ μμ.
νμ§λ§ ν μλ£κ΅¬μ‘°κ° λ§μ΄ νμ©λκ³ μμΌλ©°, μ΄λ ν¨κ» λ°λΌμ€λ κ°λ
μ΄ ν μνΈ
# ν μνΈκ° μ μ©ν λ
κ°μ₯ ν¬κ±°λ κ°μ₯ μμ κ°μ ꡬν λ
μ΅μ ν or μ΅λ νμ λ£¨νΈ κ°μ΄κΈ° λλ¬Έμ νλ²μ ν ꡬμ±μ ν΅ν΄ ꡬνλ κ²μ΄ κ°λ₯
μ΅λ k λ§νΌ λ¨μ΄μ§ μμλ€μ μ λ ¬ν λ
μ½μ μ λ ¬λ³΄λ€ λμ± κ°μ λ κ²°κ³Όλ₯Ό μ»μ΄λΌ μ μμ
# μ 체 μμ€ μ½λ
private void solve() {
int[] array = { 230, 10, 60, 550, 40, 220, 20 };
heapSort(array);
for (int v : array) {
System.out.println(v);
}
}
public static void heapify(int array[], int n, int i) {
int p = i;
int l = i * 2 + 1;
int r = i * 2 + 2;
if (l < n && array[p] < array[l]) {
p = l;
}
if (r < n && array[p] < array[r]) {
p = r;
}
if (i != p) {
swap(array, p, i);
heapify(array, n, p);
}
}
public static void heapSort(int[] array) {
int n = array.length;
// init, max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// for extract max element from heap
for (int i = n - 1; i > 0; i--) {
swap(array, 0, i);
heapify(array, i, 0);
}
}
public static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}